/**
 *   Copyright (c) fanguangping. All rights reserved.
 *   The use and distribution terms for this software are covered by the
 *   Eclipse Public License 1.0 (http://opensource.org/licenses/eclipse-1.0.php)
 *   which can be found in the file epl-v10.html at the root of this distribution.
 *   By using this software in any fashion, you are agreeing to be bound by
 * 	 the terms of this license.
 *   You must not remove this notice, or any other, from this software.
 **/
package org.jfunny.core.dfa;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

import org.jfunny.core.ds.Arg;
import org.jfunny.core.ds.Loop;
import org.jfunny.core.ds.Statement;
import org.jfunny.core.ds.Symbol;
import org.jfunny.core.mapping.IMapping;
import org.jfunny.core.mapping.SysMapping;
import org.jfunny.core.meta.Namespace;
import org.jfunny.core.sys.ISysCallback;
import org.jfunny.core.sys.ISysEvaluator;
import org.jfunny.core.sys.SysLoader;

/**
 * 带参数的DFA（确定的有穷自动机），为保证其确定性，定义模板时需无二义性
 * 
 * @author fanguangping
 * 
 * 
 */
public class DFA {

	/**
	 * 获得单例对象
	 * @return
	 */
	public static DFA getInstance() {
		return instance;
	}

	/**
	 * 获得命名空间
	 * @param statement
	 * @return
	 */
	public Namespace getNamespace(Statement statement) {
		return this.matchSys(statement, new ISysCallback<Namespace>() {

			@Override
			public Namespace eval(String statement) {
				return SysLoader.sysEvaluator.getNamespace(statement);
			}

		});
	}

	/**
	 * 翻译前的准备
	 * @param statement
	 */
	public void prepare(Statement statement) {
		this.matchSys(statement, new ISysCallback<Void>() {

			@Override
			public Void eval(String statement) {
				SysLoader.sysEvaluator.prepare(statement);
				return null;
			}

		});
	}

	/**
	 * 系统模板模式匹配
	 * @param statement
	 * @param callback
	 * @return
	 */
	private <T> T matchSys(Statement statement, ISysCallback<T> callback) {
		List<Statement> source = statement.getChildren();

		for (IMapping mapping : SysLoader.getSysMappings()) {
			//取得模板映射DFA的开始状态
			State start = mapping.getStarter();

			//对参数进行替换的HashMap，注意HashMap的值是一个列表
			Map<String, List<Statement>> replaceMap = new HashMap<String, List<Statement>>();
			for (Statement d : source) {
				//对输入的Statement进行状态流转
				State next = start.transit(d, replaceMap);
				start = next;
				if (start == null) {
					break;
				}
			}
			//没有匹配成功，则继续循环
			if (start == null) {
				continue;
			}

			//匹配成功
			if (start.isAccept()) {
				StringBuffer buffer = new StringBuffer();
				for (Statement s : mapping.getValueTemplate()) {
					//如果为参数
					if (s instanceof Arg) {
						Statement rep = replaceMap.get(s.toString()).get(0);
						String str = ISysEvaluator.DELIMITER + rep.toString();
						buffer.append(str);
					}
					//如果为Symbol
					else {
						buffer.append(s.toString());
						buffer.append(" ");
					}
				}

				String result = buffer.toString();
				return callback.eval(result);
			}
		}

		return null;
	}

	/**
	 * 模式匹配
	 * @param statement
	 * @return
	 */
	public String match(Namespace namespace, Statement statement) {
		List<Statement> source = statement.getChildren();

		//当源语句只有一个待匹配参数时，并且有与之相同的函数名称、匹配的模板或符号，
		//则返回对应的函数名称、对应的模板值、对应的符号

		//并且有该匹配参数的模板，则直接返回匹配的模板的值
		//例如：对于映射"读取输入 -> (read)"，源语句"{读取输入}"直接返回"(read)"
		if (source != null && source.size() == 1) {
			String result = matchOneArg(namespace, source.get(0).toString());
			if (result != null) {
				return result;
			}
		}

		// 当源语句包含的子语句全部为Symbol时，直接将它们对应的字符串返回
		// 例如：对于源语句"{'(a b c)}"，直接返回"'(a b c)"
		if (source != null && source.size() > 0) {
			boolean orignal = true;
			StringBuffer buffer = new StringBuffer();
			for (int i = 0; i < source.size(); i++) {
				if (source.get(i) instanceof Symbol) {
					buffer.append(source.get(i));
					buffer.append(" ");
				}
				else {
					orignal = false;
					break;
				}
			}
			if (orignal) {
				String str = buffer.toString();
				return str;
			}
		}

		//其他情况，对语句进行模式匹配，循环遍历模板映射列表
		for (IMapping mapping : SysLoader.getUsedMappings(namespace)) {
			if ("".equals(mapping.getKey())) {
				//System.out.println("debug");	//调试用
			}

			//取得模板映射DFA的开始状态
			State start = mapping.getStarter();

			//对参数进行替换的HashMap，注意HashMap的值是一个列表
			Map<String, List<Statement>> replaceMap = new HashMap<String, List<Statement>>();
			for (Statement d : source) {
				//对输入的Statement进行状态流转
				State next = start.transit(d, replaceMap);
				start = next;
				if (start == null) {
					break;
				}
			}
			//没有匹配成功，则继续循环
			if (start == null) {
				continue;
			}

			//匹配成功
			if (start.isAccept()) {
				StringBuffer buffer = new StringBuffer();

				int index = 0;
				for (Statement s : mapping.getValueTemplate()) {

					index++;
					//如果为循环模式
					if (s instanceof Loop) {
						int matchTimes = 0; //循环匹配的次数

						List<Statement> list = s.getChildren();
						for (Statement st : list) {
							if (st instanceof Arg) {
								List<Statement> listStatement = replaceMap.get(st.toString());
								matchTimes = (listStatement == null) ? 0 : listStatement.size(); //计算循环匹配的次数
								break;
							}
						}

						StringBuffer loopBuffer = new StringBuffer();
						boolean emptyLoop = false;
						for (int i = 0; i < matchTimes; i++) {
							//String prefix = " ";
							for (Statement st : list) {
								loopBuffer.append(" "); //prefix
								if (st instanceof Arg) {
									Statement rep = replaceMap.get(st.toString()).get(i);
									//对于空语句，退出循环，不添加任何字符串
									if ("{}".equals(rep.toString())) {
										emptyLoop = true;
										break;
									}
									String str = match(namespace, rep); //递归调用模式匹配
									loopBuffer.append(str);
								}
								else {
									loopBuffer.append(st.toString());
								}
								//prefix = " ";
							}
						}
						//对于非空语句，添加展开后的字符串
						if (!emptyLoop) {
							buffer.append(loopBuffer.toString());
						}
					}
					//如果为参数
					else if (s instanceof Arg) {
						Statement rep = replaceMap.get(s.toString()).get(0);
						
						if (mapping instanceof SysMapping) {
							String str = null;
							
							List<Statement> list = ((Arg)rep).getChildren();
							
							if (list.size() == 1 && ((Symbol)list.get(0)).isCode()) {
								str = ISysEvaluator.DELIMITER + "`" + rep.toString() + "`";
							}
							else {
								str = ISysEvaluator.DELIMITER + rep.toString();
							}
							buffer.append(str);
						}
						else {
							String str = match(namespace, rep); //递归调用模式匹配
							buffer.append(str);
						}
					}
					//如果为Symbol
					else {
						buffer.append(s.toString());
						if (index < mapping.getValueTemplate().size() - 1) {
							buffer.append(" ");
						}
					}
				}

				String result = buffer.toString();
				if (mapping instanceof SysMapping) {
					result = SysLoader.sysEvaluator.eval(result);
				}

				return result;
			}
		}

		return "";
	}

	/**
	 * 当源语句只有一个待匹配参数时，并且有该匹配参数的模板，则直接返回匹配的模板的值
	 * @param source
	 * @param mappings
	 * @return
	 */
	private String matchOneArg(Namespace namespace, String symbol) {
		//匹配自定义的函数名称
		String nsSymbol = null;
		if (namespace == null || symbol.contains("/")) {
			nsSymbol = symbol;
		}
		else {
			nsSymbol = namespace.getName() + "/" + symbol;
		}
		if (SysLoader.FUNCTIONS.contains(nsSymbol)) {
			return nsSymbol;
		}

		for (IMapping mapping : SysLoader.getUsedMappings(namespace)) {
			//匹配的模板
			List<Statement> key = mapping.getKeyTemplate();
			if (key.size() == 1) {
				Statement s = key.get(0);
				if (s instanceof Symbol && symbol.equals(s.toString())) {
					return mapping.getValue();
				}
			}

			//匹配的模板对应的函数名称
			String keyName = mapping.getKeyName();
			if (keyName != null && keyName.equals(symbol)) {
				return mapping.getValueName();
			}
		}

		return null;
	}

	private int stateId = 0;

	/**
	 * 将模板转换为DFA
	 * @param pattern
	 * @return
	 */
	public State toDFA(List<Statement> pattern) {
		LinkedList<Statement> list = new LinkedList<Statement>(pattern);

		State currentState = nextState();
		State starter = currentState;

		while (list.size() > 0) {
			Statement s = list.removeFirst();

			if (s instanceof Loop) {
				Loop p = (Loop) s;
				//对于【】?模式
				if (p.getType() == Loop.ZERO_ONE) {
					State nextState1 = nextState();
					this.setTransition(currentState, nextState1, p);

					if (list.size() > 0) {
						State nextState2 = nextState();
						Statement next = list.removeFirst();

						currentState.setTransition(next, nextState2);
						nextState1.setTransition(next, nextState2);
						currentState = nextState2;
					}
					else {
						currentState.setAccept(true);
						currentState = nextState1;
					}
				}
				//对于【】*模式
				else if (p.getType() == Loop.ZERO_MORE) {
					this.setTransition(currentState, currentState, p);
					p.matchTimes = -1;
				}
				//对于【】+模式
				else if (p.getType() == Loop.ONE_MORE) {
					State nextState = nextState();
					this.setTransition(currentState, nextState, p);
					this.setTransition(nextState, nextState, p);
					currentState = nextState;
				}
			}
			else {
				State nextState = nextState();
				currentState.setTransition(s, nextState);
				currentState = nextState;
			}
		}

		currentState.setAccept(true);
		return starter;
	}

	/**
	 * 对于循环模式，设置状态转换
	 * @param current
	 * @param next
	 * @param p
	 */
	private void setTransition(State current, State next, Loop p) {
		LinkedList<Statement> list = new LinkedList<Statement>(p.getChildren());
		State currentState = current;
		while (list.size() > 1) {
			Statement s = list.removeFirst();
			State nextState = nextState();
			currentState.setTransition(s, nextState);
			currentState = nextState;
		}
		Statement s = list.removeFirst();
		currentState.setTransition(s, next);
	}

	private State nextState() {
		return new State(stateId++);
	}

	private static DFA instance = new DFA();

	private DFA() {
	}
}
